UVa/924 - Spreading the news/924.2.cpp

   1 /*
   2   Problem: 924 - Spreading the news (UVa Online Judge)
   3   Andrés Mejía-Posada (http://github.com/andmej/acm)
   4
   5   Verdict: Accepted
   6   Algorithm: Breadth-first search
   7
   8  */
   9 #include <iostream>
  10 #include <queue>
  11 #include <vector>
  12 #include <cassert>
  13 using namespace std;
  14
  15 int main(){
  16   int E;
  17   scanf("%d", &E);
  18   vector<int> g[E];
  19   for (int i=0; i<E; ++i){
  20     int N;
  21     scanf("%d", &N);
  22     while (N--){
  23       int j;
  24       scanf("%d", &j);
  25       g[i].push_back(j);
  26     }
  27   }
  28
  29   int T;
  30   scanf("%d", &T);
  31   while (T--){
  32     int start;
  33     scanf("%d", &start);
  34     if (g[start].size() == 0){
  35       printf("0\n");
  36     }else{
  37       int max_boom = -1, first_day = -1, booms[E];
  38       bool visited[E];
  39       memset(booms, 0, sizeof booms);
  40       memset(visited, false, sizeof visited);
  41       queue<pair<int, int> > q;
  42       q.push(make_pair(start, 0));
  43       while (q.size()){
  44         int person = q.front().first;
  45         int today = q.front().second;
  46         q.pop();
  47
  48         if (visited[person]) continue;
  49
  50         visited[person] = true;
  51         booms[today]++;
  52         if (today > 0 && booms[today] > max_boom){
  53           max_boom = booms[today];
  54           first_day = today;
  55         }
  56
  57         vector<int> &friends = g[person];
  58         for (int i=0; i<friends.size(); ++i){
  59           if (!visited[friends[i]]){
  60             q.push(make_pair(friends[i], today + 1));
  61           }
  62         }
  63       }
  64       assert(max_boom != -1 && first_day != -1);
  65       printf("%d %d\n", max_boom, first_day);
  66     }
  67   }
  68   return 0;
  69 }